package main

// 暴力破解很容易想到， O(n^2)时间复杂度，超时。
func numFriendRequests(ages []int) int {
	rst := 0
	for i, x := range ages {
		for j, y := range ages {
			if i == j {
				continue
			}
			if y <= int(0.5*float64(x))+7 ||
				(y > 100 && x < 100) ||
				y > x {
				continue
			}
			rst += 1
		}
	}
	return rst
}

// 数据规模 1 <= n <= 2 * 10^4, 至少是 O(nlogn)的时间复杂度才能通过。
// 这道题计数排序 + 前缀和是最优的解法。比直接排序O(nlogn)要优秀，且更快算出来rst
// 前缀和使用就很妙了，还要将上面的三个条件进行化简。看官方题解~ 我没看明白
func numFriendRequests(ages []int) (ans int) {
	const mx = 121
	var cnt, pre [mx]int
	for _, age := range ages {
		cnt[age]++
	}
	for i := 1; i < mx; i++ {
		pre[i] = pre[i-1] + cnt[i]
	}
	for i := 15; i < mx; i++ {
		if cnt[i] > 0 {
			bound := i/2 + 8
			ans += cnt[i] * (pre[i] - pre[bound-1] - 1)
		}
	}
	return
}
